중첩된 배열의 stringify 직접 구현
August 14, 2021
과제
[1, 2, ['a', [1, 2], false], 3, ['b', 'c', [1, 2]]]; 를 stringify할 것 힌트
ds stack 을 이용한다.
- 최상위 배열의 원소를 돌다가 원소가 배열인 경우를 만난다.
- 스택에 최상위 배열과 진행했던 인덱스를 담아둔다.
- 자식배열을 다시 0번 인덱스부터 돈다.
- 자식배열이 다 끝나면, 스택에서 마지막에 넣었던 정보가 자기 부모배열의 정보이므로 이를 복원해서 부모 배열과 그 인덱스를 이어서 진행한다.
- 그 와중에 문자열은 acc 하나에 계속 더해간다.
if (arr.length 끝) {
if (stack에 아무것도 없나) 진짜 끝;
else 아직 부모가 남았네, 부모 꺼내서 계속 진행
} else {
if (원소가 배열인가) {
2번상황. stack.push(현재 배열과 인덱스정보를 기록)
대상배열을 자식원소배열로 대체하고 인덱스는 0으로 초기화
} else {
acc에 문자열로 바꿔서 더해준다.
}
}위의 생각은 어떻게 도출된 것일까? 귀납적 사고 -> 추론 -> 패턴발견
귀납적사고를 해보자.
[1, 2, [‘a’, [1, 2], false], 3, [‘b’, ‘c’, [1, 2]]];
여기 등장하는 모든 원소의 공통점을 찾아 패턴화한다.
원소의 공통점을 찾으려면 원소의 속성을 찾는다.
- 모든 원소는 인덱스를 가진다.
- 모든 원소는 소속된 배열이 있다.
- 모든 원소는 값이거나 배열이다.
- 원소가 배열인 경우는 부모배열이 있는 경우와 없는 경우로 나눌 수 있다.
어떤 원소가 와도 위 4가지 경우만 처리하면 일반화된 귀납식을 꼬리최적화로 짤 수 있다.
위 공통점을 가지고 아래 순서를 거친다.
- 이건 [어떤걸 반복]해서 만들어진거지?
- 각 반복은 [이전결과]에 뭔짓을 한거지?
- 꼬리재귀 -> 루프
내 풀이
let arr = [1, 2, ['a"b', [1, 2], false], 32, ['bk\\bd', 'c', [1, 2]]];
const stringReplace = [
[/"/, '\\"'],
[/\\/, '\\'],
];
const stringify = {
number: v => v.toString(),
boolean: v => v.toString(),
string: v =>
stringReplace.reduce((acc, cur) => acc.replace(cur[0], cur[1]), v),
object: v => (Array.isArray(v) ? this.array(v) : {}),
array: v => 'null',
router(el) {
return this[typeof el]?.(el);
},
};
const stack = [];
const arrRecursive = (arr, acc, i) => {
if (i > arr.length - 1) {
if (stack.length === 0) {
return `'[${acc.substr(1)}]'`;
} else {
return arrRecursive(stack[stack.length - 1][0], acc, stack.pop()[1] + 1);
}
} else {
if (Array.isArray(arr[i])) {
stack.push([arr, i]);
return arrRecursive(arr[i], acc, 0);
} else {
return arrRecursive(arr, acc + `,${stringify.router(arr[i])}`, i + 1);
}
}
};
arrRecursive(arr, '', 0);
// `'[1,2,a\\"b,1,2,false,32,bk\bd,c,1,2]'`배열이 다 밖으로 나온다. 배열을 감싸야하는데 생각이 나지 않는다.
진화한 내 풀이
고민 끝에 stack과 start 인자를 새로 만들었다.
만약 새 배열의 시작이라면 ’[‘를 붙여준다.
배열의 끝이라면 ’]‘를 붙여준다.
대략 성공 !!!!
let arr = [1, 2, ['a"b', [1, 2], false], 32, ['bk\bd', 'c', [1, 2]]];
const stringReplace = [
[/"/, '\\"'],
[/\\/, '\\'],
];
const stringify = {
number: v => v.toString(),
boolean: v => v.toString(),
string: v =>
stringReplace.reduce((acc, cur) => acc.replace(cur[0], cur[1]), v),
object: v => (Array.isArray(v) ? this.array(v) : {}),
array: v => 'null',
router(el) {
return this[typeof el]?.(el);
},
};
const arrRecursive = (arr, acc, i, stack, start) => {
if (i > arr.length - 1) {
if (stack.length === 0) {
return `'[${acc.substr(1)}]'`;
} else {
return arrRecursive(
// 인자 부분 가독성이 떨어진다.
stack[stack.length - 1][0],
acc + ']',
stack.pop()[1] + 1,
stack
);
}
}
if (Array.isArray(arr[i])) {
stack.push([arr, i]);
return arrRecursive(arr[i], acc, 0, stack, true);
} else {
if (start) {
return arrRecursive(
arr,
acc + `,[${stringify.router(arr[i])}`,
i + 1,
stack
);
} else {
return arrRecursive(
arr,
acc + `,${stringify.router(arr[i])}`,
i + 1,
stack
);
}
}
};
arrRecursive(arr, '', 0, [], false);위 코드도 문제점이 보인다.
제일 마지막 구문이 제일 자주 실행되는것인데 제일 끝에 있다.
if문을 수정해서 위로 오게 해야 좋겠다.
쌤의 풀이
const recursive = (arr, acc, i, stack) => {
if (i < arr.length) {
const currEl = arr[i];
if (Array.isArray(currEl)) {
stack.push([arr, i + 1]);
return recursive(arr[i], acc + '[', 0, stack);
} else {
return recursive(arr, acc + arr[i] + ',', i + 1, stack);
}
} else {
const prev = stack.pop(); // 이렇게 깔끔하게..
if (prev) {
const [preArr, prevIndex] = prev; // 이렇게 깔끔하게 처리하다니
return recursive(prevArr, acc.substr(-1) + '],', preIndex, stack);
} else {
return acc.substr(-1) + ']';
}
}
};
const stringify = arr => recursive(arr, '[', 0, []);위 코드의 문제점은 조잡하다.
어디는 ’,‘를 더하고 어디는 ’[‘을 더하고 또 어디는 substr(-1)을 하고 등등..
깔끔하게 하려면 어떻게 해야할까?
totalAcc인자를 도입해야 한다.
힌트를 얻고 풀어보았다.
const recursive = (arr, acc, totalAcc, i, stack) => {
if (i < arr.length) {
if (Array.isArray(arr[i])) {
stack.push([arr, i + 1, acc]);
return recursive(arr[i], '', totalAcc, 0, stack);
} else {
if (stack.length === 0) {
return recursive(
arr,
acc,
totalAcc + `,${stringify.router(arr[i])}`,
i + 1,
stack
);
} else {
return recursive(
arr,
acc + `,${stringify.router(arr[i])}`,
totalAcc,
i + 1,
stack
);
}
}
} else {
const prev = stack.pop();
if (prev) {
const [prevArr, prevIndex, prevAcc] = prev;
if (prevAcc) {
return recursive(
prevArr,
prevAcc + `[${acc.substr(1)}]`,
totalAcc,
prevIndex,
stack
);
} else {
return recursive(
prevArr,
acc,
totalAcc + `[${acc + prevArr[prevArr.length - 1]}]`,
prevIndex,
stack
);
}
} else {
return `[${totalAcc.substr(1)}]`;
}
}
};
//'[1,2[,a\\"b[1,2],falsebk\bd,c,1,2],32]'prevAcc 가 비어있다면 스택이 없을 때 제일 처음 배열 건드는거니까 total에 바로 더하고,
있다면 acc에 더한다…는건 잘 생각한 것 같은데
실패..
진화한 쌤의 풀이
(쌤이 풀다가 totalAcc필요없다고 빼심)
const arrToString = arr => {
let accStr = '';
for (const v of arr) accStr += ',' + v;
return '[' + accStr.substr(1) + ']';
};
const recursive = (arr, acc, i, stack) => {
if (i < arr.length) {
if (Array.isArray(arr[i])) {
stack.push([arr, acc, i + 1]);
return recursive(arr[i], [], 0, stack);
} else {
acc.push(arr[i]);
return recursive(arr, acc, i + 1, stack);
}
} else {
arrToString(acc);
const prev = stack.pop();
if (prev) {
const [prevArr, prevAcc, prevIndex] = prev;
prevAcc.push(accStr);
return recursive(prevArr, prevAcc, prevIndex, stack);
} else {
return acc;
}
}
};
const stringifyArr = arr => recursive(arr, [], 0, []);arrToString 함수를 만들어서 관심분리.
